package com.agile.leetcode.array.Money;

import java.util.Arrays;

/**
 * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
 * 示例 1:
 *
 * 输入: amount = 5, coins = [1, 2, 5]
 * 输出: 4
 * 解释: 有四种方式可以凑成总金额:
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 *
 * 示例 2:
 *
 * 输入: amount = 3, coins = [2]
 * 输出: 0
 * 解释: 只用面额2的硬币不能凑成总金额3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coin-change-2
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author ChenZhangKun
 * @Date 2020/7/24 15:18
 */
public class Solution {
    public static void main(String[] args) {
        int[] array=new int[]{1, 2, 5};
        int change = change(10, array);
        int i = change_1(10);
        System.out.println(change);
        System.out.println(i);
        System.out.println("=================");
        System.out.println(Arrays.toString(change_1(10, array)));
    }
    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int x = coin; x < amount + 1; ++x) {
                dp[x] += dp[x - coin];
            }
        }
        return dp[10];
    }
    public static int change_1(int target){
        int[] dp=new int[target+1];
        if (target==0) return 0;
        if (target==1) return 1;
        if (target==2) return 2;
        if (target==3) return 3;
        if (target==4) return 3;
        if (target==5) return 4;
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        dp[4]=3;
        dp[5]=4;
        for (int i = 6; i <=target ; i++) {
            dp[i]=dp[i-1]+dp[i-5]+dp[i-2];
        }
        return dp[target];
    }
    public static int[] change_1(int target,int[] coins){
        // 创建dp数组
        int[] dp=new int[target+1];
        dp[0]=0;
        dp[1]=1;
        for (int i = 2; i < target; i++) {
            if (Arrays.asList(coins).contains(i)){
                dp[i]=dp[0]+1;
            }else {
                dp[i]=dp[i-1]+1;
            }
        }
        return dp;
    }
}
